package com.chilly.stack;

import java.util.Collections;
import java.util.LinkedList;

/**
 * 394. 字符串解码
 * 思路：字母、数字和括号看成是独立的 TOKEN，并用栈来维护
 * 遍历这个栈：
 * 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
 * 如果当前的字符为字母或者左括号，直接进栈
 * 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，
 * 此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，
 * 我们根据这个次数和字符串构造出新的字符串并进栈
 * <p>
 * 数字存放在数字栈，字符串存放在字符串栈，遇到右括号时候弹出一个数字栈，字母栈弹到左括号为止。就是逆波兰式那种题。
 *
 * <p>
 * Created by Chilly Cui on 2020/11/25.
 */
public class DecodeString {
    public static void main(String[] args) {
        String s = "3[a2[c]]";
        System.out.println(new Solution().decodeString(s).equals("accaccacc"));//预期输出：accaccacc
        String s2 = "2[abc]3[cd]ef";
        System.out.println(new Solution().decodeString(s2).equals("abcabccdcdcdef"));//预期输出：abcabccdcdcdef

        String s3 = "3[z]2[2[y]pq4[2[jk]e1[f]]]ef";
        System.out.println(new Solution().decodeString(s3));
        System.out.println(new Solution().decodeString(s3).equals("zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkefef"));

    }

    static class Solution {
        int idx;

        public String decodeString(String s) {
            LinkedList<String> stk = new LinkedList<String>();
            idx = 0;
            //如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
            while (idx < s.length()) {
                char cur = s.charAt(idx);
                if (Character.isDigit(cur)) {
                    // 获取一个数字并进栈
                    String digits = getDigits(s);
                    stk.addLast(digits);
                } else if (Character.isLetter(cur) || cur == '[') {
                    // 获取一个字母并进栈
                    stk.addLast(String.valueOf(s.charAt(idx++)));
                } else {
                    //StringBuffer strData = new StringBuffer();//不用用stringbuffer，翻转的时候会出问题
                    LinkedList<String> sub = new LinkedList<String>(); //存储需要编码的字母
                    while (!"[".equals(stk.peekLast())) {
                        sub.addLast(stk.removeLast());
                    }
                    Collections.reverse(sub); //字母翻转
                    // 左括号出栈
                    stk.removeLast();
                    // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                    int repTime = Integer.parseInt(stk.removeLast());
                    StringBuffer t = new StringBuffer();
                    String o = getString(sub);
                    // 构造字符串
                    while (repTime-- > 0) {
                        t.append(o);
                    }
                    // 将构造好的字符串入栈
                    stk.addLast(t.toString());
                    idx++;
                }
            }

            return getString(stk);
        }

        public String getDigits(String s) {
            StringBuffer ret = new StringBuffer();
            while (Character.isDigit(s.charAt(idx))) {
                ret.append(s.charAt(idx++));
            }
            return ret.toString();
        }

        public String getString(LinkedList<String> v) {
            StringBuffer ret = new StringBuffer();
            for (String s : v) {
                ret.append(s);
            }
            return ret.toString();
        }
    }
}
